# 下一个更大元素I: https://leetcode-cn.com/problems/next-greater-element-i/


# 单调栈
class Solution:
    def nextGreaterElement(self, nums1: list, nums2: list) -> list:
        """
            这道题注意看清题目是： 1. nums1 是nums2的子集 2. 没有重复元素 
            那么也就是说，求nums1中每个元素右面大于他的第一个数， 就是转变过来求 对应nums2中对应数字，右面第一个大于他的结果~
            可以使用单调栈解决问题，求出 nums2 每个元素的右面的第一个大于它的值，存入到 字典中，映射。
        """
        stack = list()
        map = dict()
        i, n = 0, len(nums2)
        # 遍历nums2
        while i < n:
            # 栈为空,或当前元素小于栈顶元素，直接加进去
            if not stack or nums2[i] < stack[-1]: stack.append(nums2[i])
            # 否则判断当前元素与栈顶的关系，如果大于，加入map
            else:
                while stack and nums2[i] > stack[-1]: map[stack.pop()] = nums2[i]
                stack.append(nums2[i])
            i += 1
        
        # 栈中剩余元素都是没有 右边最大值的，默认-1, 不需要加进来了， map.get(num, -1) 找不到时默认为-1
        # while stack: map[stack.pop()] = -1

        rst = []
        # 开始遍历nums1， 得出结果
        for num in nums1: 
            rst.append(map.get(num, -1))

        return rst



# 还可以优化，if else 的写法，变得更简洁







